package com.ryujung.sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    /**
     * 思路：
     * 随机选择pivot
     * 遍历数组，将小于p的值放左边，其他放右边
     * 
     * 递归执行
     */
    public static int[] quickSort(int[] nums) {
        // randomQuickSort(nums, 0, nums.length - 1);
        randomQuickSortStandard(nums, 0, nums.length - 1);
        return nums;
    }

    private static void randomQuickSortStandard(int[] nums, int l, int r) {
        if (l < r) {
            int pi = new Random().nextInt(r - l + 1) + l;
            int pivot = nums[pi];
            // move pivot to end,handle it in last step
            swap(nums, pi, r);

            int minIndex = l;
            for (int i = l; i < r; i++) {
                if (nums[i] <= pivot) {
                    swap(nums, minIndex++, i);
                }
            }
            // move pivot to middle position
            swap(nums, r, minIndex);

            randomQuickSortStandard(nums, l, minIndex - 1);
            randomQuickSortStandard(nums, minIndex + 1, r);
        }
    }

    /**
     * 针对[力扣排序算法](https://leetcode.cn/problems/sort-an-array/)优化
     */
    private static void randomQuickSort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int pi = new Random().nextInt(r - l + 1) + l;
        int pivot = nums[pi];
        swap(nums, pi, r);

        int min = l - 1;
        for (int i = l; i < r; i++) {
            if (nums[i] <= pivot) {
                min++;
                swap(nums, min, i);
            }
        }
        min++;
        swap(nums, r, min);

        randomQuickSort(nums, min + 1, r);

        // 跳过相同的基准值的情况,当数组中有大量重复值时，速度提高很多
        while (min - 1 >= 0 && nums[min - 1] == pivot) {
            min--;
        }
        if (min >= 0) {
            randomQuickSort(nums, l, min);
        }

    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = { 2, 1 };
        int[] arr1 = { 5, 3, 8, 6, 4 };
        int[] arr2 = { 3, 1, 4, 2, 5 };
        int[] arr3 = { 9, 7, 6, 2, 4, 3, 1, 5, 8 };

        arr = quickSort(arr);
        System.out.println(Arrays.toString(arr));
        arr1 = quickSort(arr1);
        System.out.println(Arrays.toString(arr1));
        arr2 = quickSort(arr2);
        System.out.println(Arrays.toString(arr2));
        arr3 = quickSort(arr3);
        System.out.println(Arrays.toString(arr3));
    }
}
